/**
 *  @file linklistStackBaseOperate.c
 *  @desc 使用带头结点的单链表实现的栈结构（链式栈）
 *        支持基本栈操作：初始化、入栈、出栈、查看栈顶、判空、销毁、打印等
 *        使用头节点（dummy node）简化操作逻辑
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-28 14:43
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// ======================== 类型定义 ========================

typedef int EleType;  // 可根据需要修改为 float、char、结构体等通用类型

/**
 * @brief 链式栈节点定义，使用带头节点的单链表结构
 */
typedef struct linklistStack {
    int data;                        // 节点中存储的实际数据
    struct linklistStack *next;     // 指向下一个节点的指针
} linklistStack, *stack;            // 定义 stack 为指向该结构体的指针类型

// ======================== 栈操作函数 ========================

/**
 * @brief 创建一个新节点，存储指定值
 * @param value 要存储的数据
 * @return 成功返回新节点指针，失败返回 NULL
 */
stack createNode(EleType value) {
    stack newS = (stack) malloc(sizeof(linklistStack));
    if (newS == NULL) return NULL;  // 内存分配失败
    newS->data = value;
    newS->next = NULL;
    return newS;
}

/**
 * @brief 初始化栈，创建一个头结点（不存放实际数据）
 * @param s 栈的指针地址
 */
void initStack(stack *s) {
    stack newS = createNode(0);  // 创建头结点，data 无实际意义
    if (newS == NULL) return;
    *s = newS;
}

/**
 * @brief 判断栈是否为空
 * @param s 栈指针
 * @return 空返回 true，否则 false
 */
bool isEmpty(stack s) {
    if (s == NULL || s->next == NULL) return true;  // next 为 NULL 表示无数据节点
    return false;
}

/**
 * @brief 入栈操作：头插法将数据节点插入到头结点之后
 * @param s 栈指针（必须为已初始化的栈）
 * @param value 要压入的值
 */
void push(stack s, int value) {
    stack newS = createNode(value);
    if (newS == NULL) return;     // 内存分配失败
    newS->next = s->next;         // 新节点指向原第一个数据节点
    s->next = newS;               // 头节点指向新节点
}

/**
 * @brief 出栈操作：弹出栈顶元素并释放内存
 * @param s 栈指针
 * @param value 用于接收出栈元素的值（传出参数）
 */
void pop(stack s, EleType *value) {
    if (isEmpty(s)) return;       // 栈空，不执行操作
    stack temp = s->next;         // 栈顶节点
    *value = temp->data;          // 获取栈顶元素的值
    s->next = temp->next;         // 移除栈顶
    free(temp);                   // 释放内存
}

/**
 * @brief 打印栈中所有元素（从栈顶到栈底）
 * @param s 栈指针
 */
void printStack(stack s) {
    if (s == NULL || s->next == NULL) return;  // 栈空
    stack cur = s->next;                       // 跳过头节点
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * @brief 获取栈顶元素但不弹出
 * @param s 栈指针
 * @param value 用于接收栈顶元素值（传出参数）
 * @return 栈非空返回 true，否则 false
 */
bool peek(stack s, EleType *value) {
    if (isEmpty(s)) return false;
    *value = s->next->data;
    return true;
}

/**
 * @brief 销毁栈，释放所有数据节点，但保留头节点（若希望完全销毁，可手动 free(*s)）
 * @param s 栈的地址
 */
void destroy(stack *s) {
    if (isEmpty(*s)) return;
    stack cur = (*s)->next;
    while (cur != NULL) {
        stack temp = cur;
        cur = cur->next;
        free(temp);
    }
    (*s)->next = NULL;  // 清空头结点指向，保留头节点本身
}

// ======================== 主函数测试 ========================

int main() {
    stack s = NULL;
    initStack(&s);           // 初始化栈

    // 入栈
    push(s, 1);
    push(s, 2);
    push(s, 3);              // 栈顶为 3

    // 出栈
    EleType data;
    pop(s, &data);
    printf("pop is %d\n", data);  // 输出：3

    // 打印当前栈状态
    printStack(s);           // 输出：2, 1

    // 查看栈顶元素
    EleType peekValue;
    if (peek(s, &peekValue)) {
        printf("peekValue is %d\n", peekValue);  // 输出：2
    }

    // 销毁栈中数据（保留头结点）
    destroy(&s);

    return 0;
}
